#define _CRT_SECURE_NO_WARNINGS 1
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };
typedef pair<int, int> PII;
class Solution {
public:
    vector<vector<int>> bfs(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> v(m, vector<int>(n, 0));
        vector<vector<int>> dist(m, vector<int>(n, 0));
        queue<PII> q;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    q.push({ i,j });
                    v[i][j] = 1;
                }
            }
        }


        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto it = q.front();
                q.pop();
                int x1 = it.first;
                int y1 = it.second;
                for (int j = 0; j < 4; j++) {
                    int a = dx[j] + x1;
                    int b = dy[j] + y1;

                    if (a >= 0 && a < m && b >= 0 && b < n && !v[a][b]) {
                        dist[a][b] = dist[x1][y1] + 1;
                        v[a][b] = 1;
                        q.push({ a,b });
                    }
                }

            }
        }
        return dist;
    }
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> ans(m, vector<int>(n, 0));
        return bfs(mat);
    }
};